/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lishuo
 * Date: 2023-10-13
 * Time: 17:02
 */
public class BInaryFInd {
    private static int count;
    // 归并排序
    private static void mergeSortFunc(int[] array, int start,int end){
        // 当元素个数小于等于1时，分解停止
        if (start >= end) {
            return;
        }
        // 递归分解
        int mid = (start+end)/2;
        // 左子序列[left,mid]
        mergeSortFunc(array,start,mid);
        // 右子序列[mid+1,right]
        mergeSortFunc(array,mid+1,end);
        // 合并排序
        merge(array,start,end,mid);
    }

    // 递归完成后的合并排序过程
    private static void merge(int[] array,int left,int right,int mid) {
        // 定义两个变量分别指向两个子序列的头
        int s1 = left;
        int s2 = mid+1;

        // 定义一个临时数组用来存储“和并排序”的数据
        int[] tmp = new int[right-left+1];
        // 临时数组下标
        int k = 0;
        // 进行“合并排序”的条件是两个子数组均不越界
        while (s1<=mid && s2<=right) {
            if (array[s1]<array[s2]) {
                tmp[k++] = array[s1++];
            } else {
                tmp[k++] = array[s2++];
                count += (mid - s1) + 1;
                count %= 1000000007;
            }
        }
        // 将还没走完的数组全部排入临时数组中
        while (s1<=mid) {
            tmp[k++] = array[s1++];
        }
        while (s2<=right) {
            tmp[k++] = array[s2++];
        }

        // 将排好的数据放入原来的数组中->注意: i+left找到原数组对应下标
        for (int i = 0; i < tmp.length; i++) {
            array[i+left] = tmp[i];
        }
    }

}
